#include <cstddef>
#include <iostream>
#include <stack>
#include <vector>
#include <chrono>
#include <queue>

using namespace std;

struct BiNode
{
    char data;
    BiNode* lchild;
    BiNode* rchild;

    BiNode(char data):data(data),lchild(nullptr),rchild(nullptr){}
};
using BiTree=BiNode*;//起别名，其实相当于BiNode BiTree[]

void TreePrint(void);
void Prior_Order_Traversal(void);
void Medium_Order_Traversal(void);
void Post_Order_Traversal(void);
BiNode *CreateBiTree(char *pot,char *mot,int nodenum);

/**
 * @brief 根据先序遍历和中序遍历得到二叉树链表
 * 本质上是一个找根节点的函数，
 * 
 * @param pot 先序序列
 * @param mot 中序序列
 * @param nodenum 节点数目
 * @return BiNode* 
 */
BiTree CreateBiTree(char *pot,char *mot,int nodenum)//nodenum是实验要求输入的
{
    if(nodenum<=0)
    {
        return nullptr;
    }//分支为空就返回

    char root=pot[0];
    int root_pos=0;
    while(mot[root_pos]!=root)
    {
        root_pos++;
    }

    int lnode_num=root_pos;
    int rnode_num=nodenum-root_pos-1;

    BiTree T=new BiNode(root);
    T->lchild=CreateBiTree(pot+1, mot, lnode_num);
    T->rchild=CreateBiTree(pot+lnode_num+1, mot+root_pos+1, rnode_num);

    return T;
}

//////////////////////////遍历递归实现//////////////////////////

/**
 * @brief 先序遍历(递归实现)
 * 
 * @param root 
 */
void Prior_Order_Traversal(BiTree root)
{
    if(root == nullptr)//空树
    {
        return;
    }
    cout<<root->data<<' ';
    Prior_Order_Traversal(root->lchild);
    Prior_Order_Traversal(root->rchild);
}

/**
 * @brief 中序遍历(递归实现)
 * 
 * @param root 
 */
void Medium_Order_Traversal(BiTree root)
{
    if(root == nullptr)//空树
    {
        return;
    }
    Medium_Order_Traversal(root->lchild);
    cout<<root->data<<' ';
    Medium_Order_Traversal(root->rchild);
}

/**
 * @brief 后序遍历递归实现
 * 
 * @param root 
 */
void Post_Order_Traversal(BiTree root)
{
    if(root == nullptr)//空树
    {
        return;
    }
    Post_Order_Traversal(root->lchild);
    Post_Order_Traversal(root->rchild);
    cout<<root->data<<' ';
}

//////////////////////////遍历非递归实现//////////////////////////

void PriorOrderTraversal(BiTree root)
{
    //vector<char> result;
    BiTree current=root;
    stack<BiTree> cs;

    //判断树为非空树
    if(root == nullptr)
    {
        return;
    }
    cs.push(root);//先压入根节点
    while(!cs.empty())
    {
        current=cs.top();
        cs.pop();
        cout<<current->data<<" ";
        if(current->rchild!=nullptr)
        {
            cs.push(current->rchild);
        }
        if(current->lchild!=nullptr)
        {
            cs.push(current->lchild);
        }
    }
    
}

/**
 * @brief 中序遍历非递归实现（堆栈实现）
 * 
 * @param root 树的根节点
 */
void MediumOrderTraversal(BiTree root)//这一块的都是指针
{
    BiTree current=root;
    stack<BiTree> cs;
    while(current || !cs.empty())//树是非空树且堆栈非空
    {
        if(current!=nullptr)
        {
            cs.push(current);//压入的是指针，也就是数据地址
            current=current->lchild;//
        }
        else 
        {
            current=cs.top();//读取栈顶指针
            cs.pop();//更新栈顶
            cout<<current->data<<" ";
            current=current->rchild;//遍历右子树
        }
    }
}

/**
 * @brief 后序遍历非递归实现（堆栈实现）
 * 充分应用了堆栈的性质
 * 
 * @param root 树的根节点
 */
void PostOrderTraversal(BiTree root)
{
    BiTree cur=root;//接收传入的根指针

    //初始化两个栈，一个用于读取，一个用于保存输出结果
    stack<BiTree> nodestack;
    stack<char> outputstack;

    nodestack.push(cur);
    while(!nodestack.empty())
    {
        cur=nodestack.top();//由于使用的是链表存储结构，所以其实都是地址
        nodestack.pop();
        outputstack.push(cur->data);
        if(cur->lchild!=nullptr)
        {   
            nodestack.push(cur->lchild);
        }
        if(cur->rchild!=nullptr)
        {   
            nodestack.push(cur->rchild);
        }
    }

    while(!outputstack.empty())
    {
        cout<<outputstack.top()<<" ";
        outputstack.pop();
    }

}

/**
 * @brief 层序遍历
 * 
 * @param root 
 */
void LevelOrderTraversal(BiTree root)
{
    BiTree cur=root;
    queue<BiTree> oqueue;

    oqueue.push(cur);
    while(!oqueue.empty())
    {
        cur=oqueue.front();
        oqueue.pop();
        cout<<cur->data<<" ";
        if(cur->lchild!=nullptr)
        {   
            oqueue.push(cur->lchild);
        }
        if(cur->rchild!=nullptr)
        {
            oqueue.push(cur->rchild);
        }
    }
}

int getNodeNum(BiTree root)
{
    
    return 0;
}


int main(int argc,char **argv)
{
    // BiTree root = new BiNode('A');
    // root->lchild = new BiNode('B');
    // root->rchild = new BiNode('C');
    // root->lchild->lchild = new BiNode('D');
    // root->lchild->rchild = new BiNode('E');
    // root->rchild->lchild = new BiNode('F');
    // root->rchild->rchild = new BiNode('G');

    // //递归实现遍历
    // cout<<"=============递归实现============="<<endl;
    // cout<<"=============先序遍历输出============="<<endl;
    // Prior_Order_Traversal(root);
    // cout<<endl;
    // cout<<"=============中序遍历输出============="<<endl;
    // Medium_Order_Traversal(root);
    // cout<<endl;
    // cout<<"=============后序遍历输出============="<<endl;
    // Post_Order_Traversal(root);
    // cout<<endl;
    // //非递归实现遍历,时间节省将近一半
    // cout<<"=============非递归实现============="<<endl;
    // cout<<"=============先序遍历输出============="<<endl;
    // PriorOrderTraversal(root);
    // cout<<endl;
    // cout<<"=============中序遍历输出============="<<endl;
    // MediumOrderTraversal(root);
    // cout<<endl;
    // cout<<"=============后序遍历输出============="<<endl;
    // PostOrderTraversal(root);
    // cout<<endl;
    
    // cout<<"=============层序遍历输出============="<<endl;
    // LevelOrderTraversal(root);
    // cout<<endl;


    BiTree root1;
    int samplenum=7;
    char pot[100]={"ABDEGCF"};
    char mot[100]={"DBGEAFC"};
    root1=CreateBiTree(pot, mot, samplenum);
    cout<<"后序遍历输出："<<endl;
    Post_Order_Traversal(root1);
    cout<<endl;
    Prior_Order_Traversal(root1);
    cout<<endl;
    Medium_Order_Traversal(root1);
    cout<<endl;

    return 0;
}